In the class of microprocessors where instructions are issued and executed out of order, commonly a structure is needed to determine if any dependent instructions are executed out of order thereby generating an erroneous result. This structure typically requires the relative age (as determined by the program counter) of the instructions in determining if an error occurred. Since instruction streams are very long, it is impracticable to implement a structure large enough to hold an entire stream of instructions, so a structure of limited size is used, wherein once the end of the structure is reached, the entries are wrapped around to the beginning. Additionally, the structure typically holds a variety of information on each instruction.
Assume a cyclical queue and the position of an entry in the queue determines its relative age, with entries closer to the tail pointer being older than entries closer to the head. To determine the oldest valid entry in the queue, start at the tail of the queue and check the validity of that entry. If that entry is valid, then it is the oldest entry in the queue. If that entry is not valid, then check the next entry in the queue. If that entry is valid, then it is the oldest entry in the queue; or if that entry is not valid, move to the next entry in the queue. This process is repeated until a valid entry is found or the head pointer is reached.
Searching for a valid entry in this fashion is the definition of an age function. However, such a serial process is timely and inefficient. Therefore, there is a need for a more efficient means for determining the age function in a processor.